#coding:utf8
#dfs
class Solution(object):
    def subsets(self,nums):
        res = []
        self.dfs(sorted(nums),0,[],res)
        return res

    def dfs(self, nums, index, path, res):
        res.append(path)
        for i in range(index, len(nums)):
            self.dfs(nums, i+1, path+[nums[i]], res)

#iteratively
class Solution2(object):
    def subsets(self,nums):
        res = [[]]
        for num in sorted(nums):
            res += [item + [num] for item in res]
        return res
